package com.sk.leetcode.arithmetic;

import com.alibaba.fastjson.JSON;
import com.alibaba.fastjson.JSONObject;

import java.util.HashMap;
import java.util.Map;

/**
 * 运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
 * <p>
 * 获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
 * 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，
 * 它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
 * 进阶:
 * 你是否可以在 O(1) 时间复杂度内完成这两种操作？
 * <p>
 * 示例:
 * LRUCache cache = new LRUCache(2);//缓存容量
 * <p>
 * cache.put(1,1);
 * cache.put(2,2);
 * cache.get(1);       // 返回  1
 * cache.put(3,3);    // 该操作会使得密钥 2 作废
 * cache.get(2);       // 返回 -1 (未找到)
 * cache.put(4,4);    // 该操作会使得密钥 1 作废
 * cache.get(1);       // 返回 -1 (未找到)
 * cache.get(3);       // 返回  3
 * cache.get(4);       // 返回  4
 */

public class Test146 {
    public static void main(String[] args) {
        /**
         [[10],[10,13],[3,17],[6,11],[10,5],[9,10],
         [13],[2,19],[2],[3],[5,25],[8],[9,22],[5,5],
         [1,30],[11],[9,12],[7],[5],[8],[9],[4,30],
         [9,3],[9],[10],[10],[6,14],[3,1],[3],
         [10,11],[8],[2,14],[1],[5],[4],[11,4],[12,24],
         [5,18],[13],[7,23],[8],[12],[3,27],[2,12],[5],[2,9]
         ,[13,4],[8,18],[1,7],[6],[9,29],[8,21],[5],[6,30],
         [1,12],[10],[4,15],[7,22],[11,26],[8,17],[9,29],[5],[3,4],[11,30],[12],[4,29]
         ,[3],[9],[6],[3,4],[1],[10],[3,29],[10,28],[1,20],[11,13],[3],[3,12],[3,8],[10,9]
         ,[3,26],[8],[7],[5],[13,17],[2,27],[11,15],[12],[9,19],[2,15],[3,16],[1],[12,17],
         [9,1],[6,19],[4],[5],[5],[8,1],[11,7],[5,2],[9,28],[1],[2,2],[7,4],[4,22],[7,24],[9,26],[13,28],[11,26]]
         */
        int[][] r = {{10,13},{3,17},{6,11},{10,5},{9,10},
                {13},{2,19},{2},{3},{5,25},{8},{9,22},{5,5},
                {1,30},{11},{9,12},{7},{5},{8},{9},{4,30},
                {9,3},{9},{10},{10},{6,14},{3,1},{3},
                {10,11},{8},{2,14},{1},{5},{4},{11,4},{12,24},
                {5,18},{13},{7,23},{8},{12},{3,27},{2,12},{5},{2,9}
                ,{13,4},{8,18},{1,7},{6},{9,29},{8,21},{5},{6,30},
                {1,12},{10},{4,15},{7,22},{11,26},{8,17},{9,29},{5},{3,4},{11,30},{12},{4,29}
                ,{3},{9},{6},{3,4},{1},{10},{3,29},{10,28},{1,20},{11,13},{3},{3,12},{3,8},{10,9}
                ,{3,26},{8},{7},{5},{13,17},{2,27},{11,15},{12},{9,19},{2,15},{3,16},{1},{12,17},
                {9,1},{6,19},{4},{5},{5},{8,1},{11,7},{5,2},{9,28},{1},{2,2},{7,4},{4,22},{7,24},{9,26},{13,28},{11,26}};

        LRUCache lruCache = new LRUCache(10);
        for(int[] ints : r){
            //System.out.println(JSON.toJSONString(ints));
            if(ints.length == 1){
                System.out.println(lruCache.get(ints[0]));
            }else{
                lruCache.put(ints[0], ints[1]);
            }
//            Cache cache = lruCache.first;
//            int index = 0;
//            while (cache!=null){
//                System.out.print(cache.key +":"+cache.getValue()+",");
//                cache = cache.next;
//                index++;
//            }
//            System.out.println();
//            String fir = lruCache.first==null?"null":lruCache.first.key+":"+lruCache.first.getValue();
//            String las = lruCache.last==null?"null":lruCache.last.key+":"+lruCache.last.getValue();
//            System.out.println(fir+"-"+las);
        }
    }
}

class LRUCache {
    Map<Integer, Cache> cache;
    private int capacity;
    private int size;
    public Cache first;
    public Cache last;

    public LRUCache(int capacity) {
        this.capacity = capacity;
        cache = new HashMap<>(capacity);
    }

    public int get(int key) {
        Cache ca = cache.get(key);
        if(ca == null) {
            return -1;
        }
        getChange(ca);
        return cache.get(key).getValue();
    }

    private void getChange(Cache cache) {
        if(cache.pre == null) {
            return;
        }
        if(cache.next == null) {
            last = cache.pre;
            cache.pre.next = null;
            first.pre = cache;
            cache.next = first;
            first = cache;
            cache.pre = null;
            return;
        }
        cache.pre.next = cache.next;
        cache.next.pre = cache.pre;
        first.pre = cache;
        cache.next = first;
        first = cache;
        cache.pre = null;
    }

    public void put(int key, int value) {
        if(capacity == 1) {
            if(size == 0) {
                Cache ca = new Cache(key, value);
                cache.put(key, ca);
                first = ca;
                size++;
                return;
            }
            cache.remove(first.key);
            Cache ca = new Cache(key, value);
            cache.put(key, ca);
            first = ca;
            return;
        }
        if(size == 0) {
            Cache ca = new Cache(key, value);
            first = ca;
            cache.put(key, ca);
            size = 1;
            return;
        } else if(size == 1) {
            Cache ca = cache.remove(key);
            if(ca != null) {
                ca = new Cache(key, value);
                first = ca;
                cache.put(key, ca);
                return;
            } else {
                ca = new Cache(key, value);
                cache.put(key, ca);
                first.pre = ca;
                ca.next = first;
                last =first;
                first = ca;
                size = 2;
                return;
            }
        } else {
            Cache ca = cache.remove(key);
            if(ca != null) {
                Cache cac = new Cache(key, value);
                if(ca.pre == null) {
                    ca.next.pre = cac;
                    cac.next = ca.next;
                    first = cac;
                    cache.put(key, cac);
                    return;
                }
                if(ca.next == null) {
                    last = ca.pre;
                    last.next = null;
                    first.pre = cac;
                    cac.next = first;
                    first = cac;
                    cache.put(key, cac);
                    return;
                }
                ca.pre.next = ca.next;
                ca.next.pre = ca.pre;
                first.pre = cac;
                cac.next = first;
                first = cac;
                cache.put(key, cac);
                return;
            } else {
                if(capacity > size) {
                    ca = new Cache(key, value);
                    first.pre = ca;
                    ca.next = first;
                    first = ca;
                    cache.put(key, ca);
                    size++;
                } else {
                    ca = new Cache(key, value);
                    first.pre = ca;
                    ca.next = first;
                    first = ca;
                    cache.remove(last.key);
                    cache.put(key, ca);
                    last = last.pre;
                    last.next = null;
                }
            }

        }

    }

}

class Cache {
    public Cache next;
    public Cache pre;
    public int key;
    private int value;

    public Cache(int key, int value) {
        this.key = key;
        this.value = value;
    }

    public int getValue() {
        return value;
    }
}